﻿
//void rotate(int* nums, int numsSize, int k) {
//	while (k--)
//	{
//		int end = nums[numsSize - 1];
//		for (int i = numsSize - 1; i > 0; i--)
//		{
//			nums[i] = nums[i - 1];
//		}
//		nums[0] = end;
//	}
//}

// 请计算⼀下Func1中++count语句总共执⾏了多少次？
//void Func1(int N)
//{
//	int count = 0;
//	for (int i = 0; i < N; ++i)
//	{
//		for (int j = 0; j < N; ++j)
//		{
//			++count;
//		}
//	}
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	}
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//}

// 计算Func2的时间复杂度？ 
//void Func2(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 2 * N; ++k)
//	{
//		++count;
//	}
//	int M = 10;
//	while (M--)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 计算Func3的时间复杂度？ 
//void Func3(int N, int M)
//{
//	int count = 0;
//	for (int k = 0; k < M; ++k)
//	{
//		++count;
//	}
//	for (int k = 0; k < N; ++
//		k)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 计算Func4的时间复杂度？ 
//void Func4(int N)
//{
//	int count = 0;
//	for (int k = 0; k < 100; ++k)
//	{
//		++count;
//	}
//	printf("%d\n", count);
//}

// 计算strchr的时间复杂度？ 
//const char* strchr(const char* str, int character)
//{
//	const char* p_begin = s;
//	while (*p_begin != character)
//	{
//		if (*p_begin == '\0')
//			return NULL;
//		p_begin++;
//	}
//	return p_begin;
//}

// 计算BubbleSort的时间复杂度？ 
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}

//void func5(int n)
//{
//	int cnt = 1;
//	while (cnt < n)
//	{
//		cnt *= 2;
//	}
//}
//
//// 计算阶乘递归Fac的时间复杂度？ 
//long long Fac(size_t N)
//{
//	if (0 == N)
//		return 1;
//	return Fac(N - 1) * N;
//}

// 计算BubbleSort的时间复杂度？ 
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i - 1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange == 0)
//			break;
//	}
//}

//// 计算阶乘递归Fac的空间复杂度？ 
//long long Fac(size_t N)
//{
//	if (N == 0)
//		return 1;
//
//	return Fac(N - 1) * N;
//}

//void rotate(int* nums, int numsSize, int k) {
//	while (k--)
//	{
//		int end = nums[numsSize - 1];
//		for (int i = numsSize - 1; i > 0; i--)
//		{
//			nums[i] = nums[i - 1];
//		}
//		nums[0] = end;
//	}
//}

void rotate(int* nums, int numsSize, int k) {
	while (k--)
	{
		int end = nums[numsSize - 1];
		for (int i = numsSize - 1; i > 0; i--)
		{
			nums[i] = nums[i - 1];
		}
		nums[0] = end;
	}
}


void rotate(int* nums, int numsSize, int k)
{
	int newArr[numsSize];
	for (int i = 0; i < numsSize; ++i)
	{
		newArr[(i + k) % numsSize] = nums[i];
	}
	for (int i = 0; i < numsSize; ++i)
	{
		nums[i] = newArr[i];
	}
}

//逆置函数
void my_reverse(int* nums, int left, int right)
{
	while (left < right)
	{
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;

		left++;
		right--;
	}
}
void rotate(int* nums, int numsSize, int k)
{
	k = k % numsSize;
	//前n - k个逆置
	my_reverse(nums, 0, numsSize - 1 - k);
	//后k个逆置
	my_reverse(nums, numsSize - k, numsSize - 1);
	//
	my_reverse(nums, 0, numsSize - 1);
}